#define _CRT_SECURE_NO_WARNINGS
class Solution {
public:
    int findMaxForm(vector<string>& strs, int m, int n) {
        int k = strs.size();
        vector<vector<vector<int>>> dp(k + 1, vector<vector<int>>(m + 1, vector<int>(n + 1, 0)));
        for (int i = 1; i <= k; i++)
        {
            //cout<<i<<":";
            for (int j = 0; j <= m; j++)
            {
                //cout<<j<<endl;
                for (int k = 0; k <= n; k++)
                {
                    int a = 0;//'0'
                    int b = 0;//'1'
                    for (auto e : strs[i - 1])
                    {
                        if (e == '0')
                            a++;
                        else
                            b++;
                    }
                    dp[i][j][k] = dp[i - 1][j][k];
                    //cout<<a<<":"<<b<<" ";
                    if (j >= a && k >= b)
                    {
                        dp[i][j][k] = max(dp[i][j][k], dp[i - 1][j - a][k - b] + 1);
                        //cout<<dp[i-1][j-a][k-b]<<":"<<dp[i-1][j-a][k-b]+1<<":";
                    }
                    //cout<<dp[i][j][k]<<" ";
                }
            }
            //cout<<endl;
        }
        return dp[k][m][n];
    }
};

class Solution {
public:
    int profitableSchemes(int n, int minProfit, vector<int>& group, vector<int>& profit) {
        int n1 = group.size();
        vector<vector<vector<int>>> dp(n1 + 1, vector<vector<int>>(n + 1, vector<int>(minProfit + 1, 0)));
        dp[0][0][0] = 0;
        long long mod = 1e9 + 7;
        for (int i = 0; i <= n; i++)
            dp[0][i][0] = 1;
        for (int i = 1; i <= n1; i++)
        {
            //cout<<i<<":";
            for (int j = 0; j <= n; j++)
            {
                //cout<<j<<endl;
                for (int k = 0; k <= minProfit; k++)
                {
                    dp[i][j][k] = dp[i - 1][j][k];
                    if (j >= group[i - 1])
                    {
                        dp[i][j][k] += dp[i - 1][j - group[i - 1]][max(0, k - profit[i - 1])];
                    }
                    dp[i][j][k] %= mod;
                    //cout<<dp[i][j][k]<<" ";
                }
            }
            //cout<<endl;
        }
        return dp[n1][n][minProfit];
    }
};

class Solution {
public:
    int combinationSum4(vector<int>& nums, int target) {
        vector<unsigned int> dp(target + 1, 0);
        int n = nums.size();
        dp[0] = 1;
        for (int i = 0; i <= target; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (i >= nums[j])
                    dp[i] += dp[i - nums[j]];
            }
        }
        return dp[target];
    }
};

class Solution {
public:
    int numTrees(int n) {
        vector<int> dp(n + 1, 0);
        dp[0] = 1;
        //dp[1] = 1;
        for (int i = 1; i <= n; i++)
        {
            for (int j = 0; j < i; j++)
            {
                dp[i] += dp[j] * dp[i - 1 - j];
            }
        }
        return dp[n];
    }
};